#define DEBUG
#include <cstdio>
#include <cassert>
#define MODS 1000000007
#define MAXM 60
#define MAX_HASH_SIZE 1000003

using namespace std;

class ThreeTuple {
public:
  long long a, b, c;

  ThreeTuple() {
    a=b=c=0;
  }

  ThreeTuple(long long a, long long b, long long c) {
    this->a=a, this->b=b, this->c=c;
  }

  bool operator==(ThreeTuple x) {
    return a==x.a && b==x.b && c==x.c;
  }

  int operator%(int x) {
    return a%x*b%x+c%x;
  }
};

class TwoTuple {
public:
  long long a, b;

  TwoTuple() {
    a=b=0;
  }

  TwoTuple(long long a, long long b) {
    this->a=a, this->b=b;
  }

  bool operator==(TwoTuple x) {
    return a==x.a && b==x.b;
  }

  int operator%(int x) {
    return a%x*(x-1)%x*b%x;
  }
};

template<class T>
class Hash {
public:
  int val[MAX_HASH_SIZE], ver[MAX_HASH_SIZE], vernow;
  T book[MAX_HASH_SIZE];

  void add(T key, int val) {
    int pos = key%MAX_HASH_SIZE;
    for (; ver[pos]==vernow; pos = (pos+1)%MAX_HASH_SIZE) {
      if (book[pos]==key) {
	return;
      }
    }
    book[pos] = key;
    ver[pos] = vernow;
    this->val[pos] = val;
  }

  int get(T key) {
    int pos = key%MAX_HASH_SIZE;
    for (; ver[pos]==vernow; pos = (pos+1)%MAX_HASH_SIZE) {
      if (book[pos]==key) {
	return val[pos];
      }
    }
    return -1;
  }
};

class Tree {
public:
  Tree *a, *b;
  long long c, d, l, size, ans=-1, id;
  static Hash<ThreeTuple> *f;
  static Hash<TwoTuple> *g;

  long long dis(long long u, long long v) {
    long long ret;
    if (u==v) {
      return 0;
    }
    if ((ret=f->get(ThreeTuple(id, u, v)))>=0) {
      return ret;
    }
    if (u<a->size && v<a->size) {
      ret = a->dis(u, v);
    } else if (u<a->size && v>=a->size) {
      ret = (a->dis(u, c)+b->dis(d, v-a->size)+l)%MODS;
    } else if (u>=a->size && v<a->size) {
      ret = (a->dis(v, c)+b->dis(d, u-a->size)+l)%MODS;
    } else {
      ret = b->dis(u-a->size, v-a->size);
    }
    f->add(ThreeTuple(id, u, v), ret);
    return ret;
  }

  long long disAll(long long o) {
    long long ret;
    if (id==0) {
      return 0;
    }
    if ((ret=g->get(TwoTuple(id, o)))>=0) {
      return ret;
    }
    if (a->size>o) {
      ret = a->disAll(o)+b->disAll(d)+(dis(o, c)+l)*b->size%MODS;
    } else {
      ret = b->disAll(o-a->size)+a->disAll(c)+(dis(o, d+a->size)*a->size%MODS);
    }
    g->add(TwoTuple(id, o), ret);
    return ret;
  }

  long long solve() {
    size = a->size+b->size;
    ans = (a->ans+b->ans + a->disAll(c)*b->size%MODS + a->size*b->disAll(d)%MODS + a->size*b->size%MODS*l%MODS)%MODS;
    return ans;
  }
};

Hash<ThreeTuple> *Tree::f = new Hash<ThreeTuple>();
Hash<TwoTuple> *Tree::g = new Hash<TwoTuple>();

int main() {
#ifdef DEBUG
  freopen("4211.in", "r", stdin);
  freopen("4211.out", "w", stdout);
#endif

  int t;
  scanf("%d", &t);
  for (int ti=1; ti<=t; ti++) {
    static Tree tree[MAXM+1];
    int m;
    scanf("%d", &m);
    tree[0].size = 1, tree[0].ans=0, tree[0].id=0;
    Tree::f->vernow++, Tree::g->vernow++;
    for (int i=1; i<=m; i++) {
      int a, b;
      scanf("%d %d %lld %lld %lld", &a, &b, &tree[i].c, &tree[i].d, &tree[i].l);
      tree[i].id = i, tree[i].a = &tree[a], tree[i].b = &tree[b];
      printf("%lld\n", tree[i].solve());
    }
  }

  fcloseall();
  return 0;
}
